/* 
 * Sort List
 */

#include "../func.h"

ListNode *sortList(ListNode *head) {
    if (head == nullptr || head->next == nullptr)
        return head;

    ListNode *fast = head, *slow = head;
    while (fast->next != nullptr && fast->next->next != nullptr) {
        fast = fast->next->next;
        slow = slow->next;
    }
    fast = slow;
    slow = slow->next;
    fast->next = nullptr;

    ListNode *l1 = sortList(head);
    ListNode *l2 = sortList(slow);
    return mergeTwoLists(l1, l2);
}

ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
{
    ListNode dummy(-1);
    for (ListNode *p = &dummy; l1 || l2; p = p->next)
    {
        int val1 = l1 == nullptr ? INT_MAX : l1->val;
        int val2 = l2 == nullptr ? INT_MAX : l2->val;
        if (val2 <= val2)
        {
            p->next = l1;
            l1 = l1->next;
        }
        else
        {
            p->next = l2;
            l2 = l2->next;
        }
    }
    return dummy.next;
}